class Solution {
public:     
    const static int mod = 1e9 + 7;
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int len = group.size();
        
        vector<vector<int>> dp(n+1,vector<int>(minProfit+1));
        dp[0][0] = 1;
        for(int i = 0;i <= n;i++){
            dp[i][0] = 1;
        }
        int ret = 0;
        
        for(int i = 0;i < len;i++){
            for(int j = minProfit;j >= 0;j--){
                for(int k = n;k >= 0;k--){
                    int u = max(0,j-profit[i]);
                    if(k >= group[i]){
                        dp[k][j] = (dp[k][j] + dp[k-group[i]][u]) % mod;
                    }
                }
            }
        }
        
        return dp[n][minProfit];
    }
};
